package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1879. 两个数组最小的异或值之和
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/11 17:33
 */
public class MinimumXORSum {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int range = 1 << n;
        int[] dp = new int[range];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < range; i++) {
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    dp[i] = Math.min(dp[i], dp[i ^ (1 << j)] + (nums1[Integer.bitCount(i) - 1] ^ nums2[j]));
                }
            }
        }
        return dp[range - 1];
    }

}
